#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#define MAX_LINE 1024
typedef struct Grammar{
	char grammar[20]; //用来保存输入的文法
	struct Grammar *next; //用链表来保存文法
}Grammar;
typedef struct State{
	char Name;     //状态名称
	struct State *next;
	char tag;//用来区分是起始态  S  、 中间态  M  还是终态  T;
}State;
typedef struct F{  			 //状态转换函数记录
	struct State *StartState; //起点状态 非初态
	char input;				//输入的字符
	struct State *EndState;	//到达的状态
	struct F *next;
}F;
typedef struct LinkNode{
	char data;
	struct LinkNode *next;
}*LiStack;
void InitStack(LiStack *s){
	printf("栈初始化中....\n");
	//生成一个头结点
	*s = (LiStack) malloc(sizeof(struct LinkNode));
	if(*s == NULL){
		printf("malloc fail\n");
		exit(0);
	}
	printf("栈初始化成功！！\n");
	(*s)->next = NULL;
}
bool StackEmpty(LiStack S){
	if(S->next == NULL){ //如果头节点下一个节点为空，就可以说明这个栈为空栈
		return true;
	}
	else {
		return false;
	}
}
bool Push(LiStack S,char x){
	LiStack newNode = (LiStack) malloc(sizeof(struct LinkNode));
	newNode->data = x;
	//头插法
	newNode->next = S->next;
	S->next = newNode;
	return true;
}
bool Pop(LiStack S){
	if(StackEmpty(S)){
		return false;
	}
	LiStack temp = NULL;
	//删除栈顶元素节点
	temp = S->next;
	S->next = temp->next;
	free(temp);
	return true;
}
bool BracketsMatch(LiStack S,char ch[],FILE *pf,int lineNum){
	//printf("%s\n",ch);
	for(int i=0;i<strlen(ch);i++){
		if(ch[i] == '(')//入栈
		{
			Push(S, ch[i]);
		}
		else if(ch[i] == ')'){
			//出来一个
			if(!Pop(S)){
				fprintf(pf, "编译失败:发现错误,第%d行,第%d列,\"%c\"括号不匹配\n",lineNum,i+1,ch[i]);
				return false;
			}
		}
	}
	if(StackEmpty(S)){
		return true;
	}
	else {
	fprintf(pf, "编译失败:发现错误,第%d行,\"(\"括号不匹配\n",lineNum);
		return false;
	}
}
bool GetTop(LiStack S,char *x){
	if(StackEmpty(S)){
		return false;
	}
	*x = S->next->data;
	return true;
}
State *S = NULL;
void GrammarListInit(Grammar **g){
	//这个只是用来生成头结点的，不存储文法内容
	*g = (Grammar*) malloc(sizeof(Grammar));
	(*g)->next = NULL;
}
void InsertGrammar(Grammar *g,char grammar[]){  //输入文法内容
	Grammar *newNode = (Grammar*) malloc(sizeof(Grammar));
	//这里采用头插法创建
	newNode->next = g->next;
	g->next = newNode;
	strcpy(newNode->grammar, grammar);
}
void StateListInit(State **s){
	*s = (State*) malloc(sizeof(State));
	(*s)->next = NULL;
}
State* InsertState(State *stateList,char name){  //输入文法内容
	State *newNode = (State*) malloc(sizeof(State));
	//这里采用头插法创建
	newNode->next = stateList->next;
	stateList->next = newNode;
	newNode->Name = name;
	newNode->tag = 'M';//先全部假设为中间态
	return newNode;
}
State* SearchStateByName(State *stateList,char name){
	State *p = stateList->next;
	while (p) {
		if (p->Name == name) {
			return p;
		}		
		p = p->next;
	}
	return NULL;
}
void SetTagForStateList(State *stateList,char name,char tag){
	if(tag == 'S'){
		S= SearchStateByName(stateList, name);
		S->tag = 'S';
		return;
	}
	SearchStateByName(stateList, name)->tag = tag;
}
void InserF(F *fList,State *StartState,State *EndState,char input){
	F *newNode = (F*) malloc(sizeof(F));
	//这里采用头插法创建
	newNode->next = fList->next;
	fList->next = newNode;
	newNode->StartState = StartState;
	newNode->EndState = EndState;
	newNode->input = input;
}
void LookThroughGrammarList(Grammar *g,State *stateList,F *fList){
	Grammar *p = g->next;
	while (p) {
		InsertState(stateList,p->grammar[0]);
		p = p->next;
	}
	p = g->next;
	char input;
	State *StartState,*EndState;
	//生成自动机状态图
	while (p) {
		StartState = SearchStateByName(stateList,p->grammar[0]);
		for(int i=0;i<strlen(p->grammar);i++){
			//我们可以发现，终结字符是由小写字符构成 其asci码属于  97 -- 122
			//状态有大写构成 其asci码  属于 65--90
			//这里需要考虑其他情况
			if(p->grammar[i]>=97 && p->grammar[i]<=122 &&
				p->grammar[i+1]>=65 && p->grammar[i+1]<=90){
		EndState = SearchStateByName(stateList, p->grammar[i+1]);
				input = p->grammar[i];
			InserF(fList, StartState, EndState, input);
			}
			
		}
		p = p->next;
	}
}
void FListInit(F **f){
	//这个只是用来生成头结点的，不存储内容
	*f = (F*) malloc(sizeof(F));
	(*f)->next = NULL;
	(*f)->StartState = NULL;
	(*f)->EndState = NULL;
}
void PrintState(State *stateList){
	State *p = stateList->next;
	while (p) {
		printf("%c----%c\n",p->Name,p->tag);
		p = p->next;
	}
}
void PrintF(F *fList){
	F *p = fList->next;
	while (p) {
		printf("%c + ",p->StartState->Name);
		printf("%c",p->input);
		printf(" = %c\n",p->EndState->Name);
		p = p->next;
	}
}
void PrintGrammar(Grammar *g){
	Grammar *p = g->next;
	while (p) {
		printf("%s\n",p->grammar);
		p = p->next;
	}
}
bool DFA(F *fList,char input[],LiStack stack,int lineNum,FILE *pf){
	State *NowSate = S;//将一开始的状态设置为初态
	F *p = NULL;
	bool isCheckBrackets = false;
	bool BracketsMatched = true;
	char token[40];
	bool isDigital = false;
	bool isFloat = false;
	bool isID = false;
	int index = 0;
	char errorChar;
	int errorCol;
	for(int i=0;i<strlen(input);i++){
		index = 0;
		if(input[i] == ';'){
			fprintf(pf,"(0,';')\n");
			break;
		}
		else if(input[i] == '(' && !isCheckBrackets){
			//printf("来检查括号拉！！");
			isCheckBrackets = true;//说明这个语句以及经过括号检查
			if(!BracketsMatch(stack,input,pf,lineNum)){
				//BracketsMatched = false;
//				fprintf(pf, "编译失败:发现错误,括号不匹配\n");
//				printf("括号不匹配\n");
				return false;
			}	
	    }
		int a,b,c;
		if(input[i] != ' '){
			p = fList->next;
			while (p) {
				if(p->StartState == NowSate ){
					if(p->input == 'd' && input[i] >= '0' && input[i] <= '9'){ //数字
						//printf("是数字\n");
						if(!isID && !isDigital){ //如果之前的不是ID的话,那么就要输出数字了
							isDigital = true;
							int j = i+1;
							//printf("是数字\n");
							token[index++] = input[i];
							while (isnumber(input[j])||input[j] == '.') {
								if(input[j] == '.'){
									isFloat = true;
								}
								token[index++] = input[j];
								j++;
							}
							token[index] = '\0';
							if(isFloat){
								fprintf(pf,"(20,'%s')\n",token);
							}
							else {
								fprintf(pf,"(10,'%s')\n",token);
							}
							isFloat = false;
						}
						NowSate = p->EndState;
						errorChar = input[i];
						errorCol = i;
						break;
					}
					else if (p->input == '.' && input[i] == '.'){
						//小数点
						NowSate = p->EndState;
						errorChar = '.';
						errorCol = i;
						break;
					}
					else if (p->input == 'l' && (input[i] >= 'a' && input[i] <= 'z') ||
						(input[i] >= 'A' && input[i] <= 'Z')){
							//printf("字母\n");
							isDigital = false;
							if(!isID){
								isID =true;
								int j = i+1;
								token[index++] = input[i];
								while (isalnum(input[j++])) {
									token[index++] = input[j-1];
								}
								token[index] = '\0';
								fprintf(pf,"(100,'%s')\n",token);
							}
							NowSate = p->EndState;
							errorChar = input[i];
							errorCol = i;
							break;
						}
					else if (p->input == '=' && input[i] == '='){
						isID = false;
						errorChar = '=';
						errorCol = i;
						fprintf(pf,"(30,'=')\n");
						NowSate = p->EndState;
						break;
					}
					else if (p->input == 'c' && (input[i] == '+' || input[i] == '-'||input[i] == '*'||input[i] == '/')){
						isID = false;
						isDigital = false;
						errorCol = i;
						switch (input[i]) {
							case '+':
								errorChar = '+';
								fprintf(pf,"(40,'+')\n");
								break;
							case '-':
								errorChar = '-';
								fprintf(pf,"(50,'-')\n");
								break;
							case '*':
								errorChar = '*';
								fprintf(pf,"(60,'*')\n");
								break;
							case '/':
								errorChar = '/';
								fprintf(pf,"(70,'/')\n");
								break;
							default:printf("Error\n");
						}
						NowSate = p->EndState;
						break;
					}
					else if (p->input == '(' && input[i] == '(' ){
						isID = false;
						isDigital = false;
						fprintf(pf,"(80,'(')\n");
						NowSate = p->EndState;
						break;
					}
					else if (p->input == ')' && input[i] == ')' ){
						isID = false;
						isDigital = false;
						fprintf(pf,"(90,')')\n");
						NowSate = p->EndState;
						break;
					}
					
				}
				p = p->next;
			}
			if(p == NULL){
				fprintf(pf,"编译失败:发现了错误语法，错误在第%d行，第%d列的\"%c\"附近\n",lineNum,i+1,errorChar);
				return false;
			}
		}
	}
	if(NowSate->tag =='T'){
		return true;
	}
	else {
		fprintf(pf,"编译失败:发现了错误语法，错误在第%d行，第%d列的\"%c\"附近\n",lineNum,errorCol+1,errorChar);
		return false;
	}
	
}
int main(int argc, char *argv[]) {
	Grammar *g = NULL;
	State *stateList = NULL;
	F *fList = NULL;
	StateListInit(&stateList);
	GrammarListInit(&g);
	FListInit(&fList);
//	InsertGrammar(g, "S->aU|bV");
//	InsertGrammar(g, "U->bV|aQ");
//	InsertGrammar(g, "V->aU|bQ");
//	InsertGrammar(g, "Q->aQ|bQ");
//	PrintGrammar(g);
//	LookThroughGrammarList(g, stateList,fList);
//	SetTagForStateList(stateList, 'S', 'S');
//	SetTagForStateList(stateList, 'Q', 'T');
//	DFA(fList,"aa");
//	InsertState(stateList, 'S');
//	InsertState(stateList, 'A');
//	InsertState(stateList, 'B');
//	InsertState(stateList, 'C');
	char StateName[24]={'S','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P'};
	for(int i=0;i<strlen(StateName);i++){
		InsertState(stateList, StateName[i]);
	}
	SetTagForStateList(stateList,'S','S');
	SetTagForStateList(stateList,'A','T');
	SetTagForStateList(stateList,'C','T');
	SetTagForStateList(stateList,'D','T');
	SetTagForStateList(stateList,'G','T');
	SetTagForStateList(stateList,'N','T');
	InserF(fList, SearchStateByName(stateList, 'S'),SearchStateByName(stateList, 'A'), 'd');
	InserF(fList, SearchStateByName(stateList, 'A'),SearchStateByName(stateList, 'A'), 'd');
	InserF(fList, SearchStateByName(stateList, 'A'),SearchStateByName(stateList, 'B'), '.');
	InserF(fList, SearchStateByName(stateList, 'B'),SearchStateByName(stateList, 'C'), 'd');
	InserF(fList, SearchStateByName(stateList, 'C'),SearchStateByName(stateList, 'C'), 'd');
	InserF(fList, SearchStateByName(stateList, 'S'),SearchStateByName(stateList, 'D'), 'l');
	InserF(fList, SearchStateByName(stateList, 'D'),SearchStateByName(stateList, 'D'), 'l');
	InserF(fList, SearchStateByName(stateList, 'D'),SearchStateByName(stateList, 'D'), 'd');
	InserF(fList, SearchStateByName(stateList, 'D'),SearchStateByName(stateList, 'E'), '=');
	InserF(fList, SearchStateByName(stateList, 'E'),SearchStateByName(stateList, 'A'), 'd');
	InserF(fList, SearchStateByName(stateList, 'E'),SearchStateByName(stateList, 'G'), 'l');
	InserF(fList, SearchStateByName(stateList,'A'),SearchStateByName(stateList, 'E'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'C'),SearchStateByName(stateList, 'E'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'G'),SearchStateByName(stateList, 'G'), 'l');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'G'),SearchStateByName(stateList, 'G'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'G'),SearchStateByName(stateList, 'E'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'G'),SearchStateByName(stateList, 'E'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'E'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'F'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'F'),SearchStateByName(stateList, 'I'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'F'),SearchStateByName(stateList, 'L'), 'l');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'I'),SearchStateByName(stateList, 'I'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'I'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'I'),SearchStateByName(stateList, 'J'), '.');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'I'),SearchStateByName(stateList, 'M'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'I'),SearchStateByName(stateList, 'N'), ')');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'J'),SearchStateByName(stateList, 'K'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'K'),SearchStateByName(stateList, 'K'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'K'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'K'),SearchStateByName(stateList, 'N'), ')');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'K'),SearchStateByName(stateList, 'M'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'N'),SearchStateByName(stateList, 'N'), ')');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'N'),SearchStateByName(stateList, 'O'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'O'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'O'),SearchStateByName(stateList, 'G'), 'l');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'O'),SearchStateByName(stateList, 'A'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'K'),SearchStateByName(stateList, 'M'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'M'),SearchStateByName(stateList, 'L'), 'l');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'M'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'M'),SearchStateByName(stateList, 'I'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'K'),SearchStateByName(stateList, 'M'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'F'),SearchStateByName(stateList, 'L'), 'l');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'F'),SearchStateByName(stateList, 'I'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'L'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'L'),SearchStateByName(stateList, 'N'), ')');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'L'),SearchStateByName(stateList, 'L'), 'l');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'L'),SearchStateByName(stateList, 'L'), 'd');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'L'),SearchStateByName(stateList, 'M'), 'c');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'S'),SearchStateByName(stateList, 'F'), '(');//c表示运算符
	InserF(fList, SearchStateByName(stateList,'D'),SearchStateByName(stateList, 'E'), 'c');//c表示运算符
	LiStack stack = NULL;
	InitStack(&stack);
//	DFA(fList,"a3123=(123.12+212)+(b21+0.2123)",stack,1);
//	DFA(fList,"aaaa3123bbb=(123.12+a212)++b*(112+21)",stack,1);
//	DFA(fList,"aaaa3123bbb=(123.12+a212)))++b*(112+21)",stack,1);
//	DFA(fList,"aaaa3123bbb=(bb123.12+a212)+b*(112+21)",stack,1);
	
	char buf[MAX_LINE];  /*缓冲区*/
	FILE *fp;            /*文件指针*/
	int len;             /*行字符个数*/
	if((fp = fopen("input.txt","r")) == NULL)
		{
			perror("fail to read");
			exit (1) ;
		}
	FILE *pf = fopen("output.txt","w+");
	fprintf(pf, "界符:0 标识符:100;  整形:10;  浮点型:20;  =:30;  +:=40  -:50  *:60  /:70  (:80 ):90\n");
	int lineNum = 0;
	while(fgets(buf,MAX_LINE,fp) != NULL)
		{
			lineNum++;
			len = strlen(buf);
			buf[len-1] = '\0';  /*去掉换行符*/
			printf("%s\n",buf);
			if(buf[len-2]!=';'){
				fprintf(pf, "编译失败:发现语法错误;第%d行，第%d列缺少';'错误\n",lineNum,len);
				exit(0);
			}
//			buf[len-2] = '\0';/*去掉';'*/
			if(!DFA(fList, buf, stack, lineNum,pf)){
				fclose(fp);
				fclose(pf);
				exit(0);
			}
		}
	fprintf(pf, "编译成功!\n");
	fclose(fp);
	fclose(pf);
}